864F - Cities Excursions - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define	rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define	dec(i, a, b)	for (int i(a); i >= (b); --i)

#ifndef ONLINE_JUDGE
class test {
	public:
		test() {
			freopen("1.txt", "r", stdin);
			freopen("2.txt", "w", stdout);
		}
} file_io;
#endif

const int N = 3e3 + 10;
const int M = 4e5 + 10;

struct query {
	int s;
	int k;
	int id;
} ;

vector <query> w[M];
vector <int> v[N], e[N];


int n, m, q;
int f[N][15];
int ans[M];
bool vis[N];


int go(int x, int k) {
	dec(i, 13, 0) {
		if ((k >> i) & 1) {
			x = f[x][i];
		}
	}
	return x;
}


void dfs(int x) {
	if (vis[x]) {
		return;
	}

	vis[x] = 1;

	for (auto u : e[x]) {
		dfs(u);
	}
}

int main() {
	
	scanf("%d%d%d", &n, &m, &q);

	rep(i, 1, m) {
		int x, y;
		scanf("%d%d", &x, &y);
		v[x].emplace_back(y);
		e[y].emplace_back(x);
	}

	rep(i, 1, q) {
		int s, t, k;
		scanf("%d%d%d", &s, &t, &k);
		w[t].push_back({s, k, i});
	}

	rep(t, 1, n) {
		if (w[t].empty()) {
			continue;
		}

		memset(f, -1, sizeof f);
		memset(vis, false, sizeof vis);

		dfs(t);

		// printf("%d : \n", t);
		// rep(i, 1, n) if (vis[i]) printf("%d ", i); putchar(10);

		rep(i, 1, n) {
			if (i == t || !vis[i]) {
				continue;
			}

			int nxt = 1e9;
			for (auto u : v[i]) {
				if (vis[u] && u < nxt) {
					nxt = u;
				}
			}
			
			f[i][0] = nxt;
		}

		// rep(i, 1, n) printf("%d ", f[i][0]); putchar(10);

		f[t][0] = t;

		rep(j, 0, 13) {
			rep(i, 1, n) {
				if (f[i][j] == -1) {
					continue;
				}
				f[i][j + 1] = f[f[i][j]][j];
			}
		}

		for (const auto& [s, k, id] : w[t]) {
			if (!vis[s]) {
				ans[id] = -1;
			}

			if (go(s, 3001) != t) {
				ans[id] = -1;
				continue;
			}

			if (k == 1) {
				ans[id] = s;
				continue;
			}

			if (go(s, k - 2) == t) {
				ans[id] = -1;
				continue;
			}

			ans[id] = go(s, k - 1);
		}
	}

	rep(i, 1, q) {
		printf("%d\n", ans[i]);
	}



	return 0;
}